//133.克隆图
//https://leetcode.cn/problems/clone-graph
class Solution {
    unordered_map<Node*,Node*> hash;
public:
    Node* cloneGraph(Node* node) {
        if(node == nullptr) return node;
        queue<Node*> q;
        q.push(node);
        hash[node] = new Node(node->val);

        while(q.size())
        {
            Node* nd = q.front(); q.pop();
            for(Node* ck:nd->neighbors)
            {
                //该节点没有访问过
                if(hash.count(ck) == 0)
                {
                    hash[ck] = new Node(ck->val);
                    q.push(ck);
                }
                hash[nd]->neighbors.push_back(hash[ck]);
            }
        }
        return hash[node];
    }
};